package structure;


import java.util.Arrays;

public class Heap4 {
    public static final int DEFAULT_CAPACITY = 11;
    int[] queue;
    private int size;

    public Heap4() {
        this.queue = new int[DEFAULT_CAPACITY];
    }

    public void init(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            queue[i] = nums[i];
            size++;
        }
    }

    public void creatHeap() {
        for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) {
            downward(parent, size);
        }
    }

    // 构建小根堆
    private void downward(int parent, int size) {
        int child = 2 * parent + 1;
        while(child < size) {
            // 在孩子节点中选择最小的那个
            if(child + 1 < size && queue[child + 1] < queue[child]) {
                child = child + 1;
            }

            // 交换孩子节点和父节点
            if(queue[child] < queue[parent]) {
                swap(queue, child, parent);

                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public void offer(int val) {
        if (isFull()) {
            queue = Arrays.copyOf(queue, 2 * queue.length);
        }
        int i = size;
        size++;
        if (i == 0) {
            queue[0] = val;
        }else {
            upward(val, i);
        }
    }

    private void upward(int val, int child) {
        while (child > 0) {
            int parent = (child - 1) / 2;
            if (val < queue[parent]) {
                queue[child] = queue[parent];
                child = parent;
            }else {
                break;
            }
        }
        queue[child] = val;
    }

    private boolean isFull() {
        return size == queue.length;
    }

    // 堆的删除
    public Integer poll() {
        if (size == 0) {
            return null;
        }
        int old = queue[0];
        swap(queue,0, size - 1);
        size--;
        downward(0, size);
        return old;
    }


}
